# 对于有序列表的查找，可以使用二分查找，查找成功返回位置，查找失败则返回null，时间复杂度为O(logn)

def binary_search(arr, item):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if item == arr[mid]:
            return mid
        if item >= arr[mid]:
            low = mid + 1
        else:
            high = mid - 1
    return None


def binary_search_recursive(arr, item, low, high):
    if low > high:
        return None
    mid = (low + high) // 2
    if item == arr[mid]:
        return mid
    if item < arr[mid]:
        high = mid - 1
    else:
        low = mid + 1
    return binary_search_recursive(arr, item, low, high)
